package cn.lishiyuan.algorithm.list;

import java.util.Objects;


/**
 * 双向链表
 * @param <T>
 */
public class LinkedList<T> implements LeeList<T> , Reverse{

    private Node<T> head = null;

    private Node<T> tail = null;

    private int size = 0;

    public final static class Node<T>{
        Node<T> prev = null;
        T data;
        Node<T> next = null;
    }

    public LinkedList(){}


    public LinkedList(T data){
        Node<T> node = newNode(data);
        this.head = node;
        this.tail = node;
        this.size = 1;
    }

    @Override
    public void addFirst(T data){
        Node<T> node = newNode(data);

        if (isEmpty()) {
            tail = node;
        }else {
            // 本节点的后继是之前的头节点
            node.next = head;
            head.prev = node;
        }

        // 本节点是新的头节点
        head = node;
        size++;
    }

    @Override
    public void addLast(T data){
        Node<T> node = newNode(data);
        if(isEmpty()) {
            // 本节点是第一个节点
            head = node;
        }else {
            // 最后一个节点
            tail.next = node;
            node.prev = tail;
        }
        tail = node;
        size++;
    }

    @Override
    public void add(int index, T data){
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        // 第一个元素
        if(index == 0){
            addFirst(data);
            return;
        }
        // 最后一个元素
        if(index == size){
            addLast(data);
            return;
        }

        // 最起码有两个元素
        Node<T> newNode = newNode(data);
        // 该位置的当前节点
        Node<T> node = findNode(index);

        if(Objects.isNull(node)){
            throw new IllegalStateException("数据异常");
        }
        // 前一个节点的后继设置为新节点
        node.prev.next = newNode;
        newNode.prev = node.prev;
        // 新节点的后一个节点是当前节点
        newNode.next = node;
        node.prev = newNode;

        size++;
    }

    @Override
    public T removeFirst(){
        if(isEmpty()){
            return null;
        }

        T data = head.data;

        // 如果只有一个节点
        if(size == 1){
            head = tail = null;
        }else {
            head = head.next;
            head.prev = null;
        }

        size--;
        return data;
    }

    @Override
    public T removeLast(){
        if(isEmpty()){
            return null;
        }
        if(size == 1){
            // 只有一个节点也就是头节点
            return removeFirst();
        }

        T data = tail.data;
        tail = tail.prev;
        tail.next = null;

        size --;
        return data;
    }

    @Override
    public T remove(int index){
        if(isEmpty()){
            return null;
        }
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        if(index == 0){
            // 只有一个节点也就是头节点
            return removeFirst();
        }

        if(index == (size - 1) ){
            return removeLast();
        }
        // 此时最少有两个节点
        // 找到该节点
        Node<T> node = findNode(index);

        if(Objects.isNull(node)){
            throw new IllegalStateException("数据异常");
        }
        // 当前上个节点的下个节点是当前节点的下个节点
        node.prev.next = node.next;
        // 当前节点的下个节点的上个节点当前节点的上个节点
        node.next.prev = node.prev;

        // 其他节点不指向当前节点，当前节点也不指向其他节点
        node.prev = null;
        node.next = null;

        size --;
        return node.data;
    }

    @Override
    public T get(int index){
        Node<T> node = findNode(index);
        if(Objects.isNull(node)){
            return null;
        }else {
            return node.data;
        }
    }

    @Override
    public int indexOf(T data){
        int nowIndex = 0;
        // 查找某个index的元素
        for(Node<T> cur = head; cur != null; cur = cur.next){
            // 查找某个data的元素
            if(Objects.equals(data, cur.data)){
                return nowIndex;
            }else {
                nowIndex ++ ;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(Object data){
        Node<T> node = findNode(data);
        return Objects.nonNull(node);
    }


    private Node<T> findNode(int index){
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        if(index == 0){
            return head;
        }

        if(index == (size-1)){
            return tail;
        }

        // 正向还是逆向查找
        int distance = size - index;

        if(index > distance){
            // 逆向查找
            int nowIndex = size - 1;
            for(Node<T> cur = tail; cur != null; cur = cur.prev){
                if(index == nowIndex){
                    return cur;
                }else {
                    nowIndex--;
                }
            }
        }else {
            // 正向查找
            int nowIndex = 0;
            for(Node<T> cur = head; cur != null; cur = cur.next){
                if(index == nowIndex){
                    return cur;
                }else {
                    nowIndex++;
                }
            }
        }
        return null;
    }


    private Node<T> findNode(Object data){

        // 查找某个index的元素
        for(Node<T> cur = head; cur != null; cur = cur.next){
            // 查找某个data的元素
            if(Objects.equals(data, cur.data)){
                return cur;
            }
        }

        return null;
    }


    // 构建节点
    private Node<T> newNode(T data){
        Node<T> node = new Node<>();
        node.data = data;
        return node;
    }


    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return head == null;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("size = ").append(size).append("; list = ");
        builder.append("[");
        Node<T> cur = head;
        while(cur != null){
            builder.append(cur.data).append(",");
            cur = cur.next;
        }

        builder.append("]");
        return builder.toString();
    }

    @Override
    public void reverse() {
        if(size < 2){
            return;
        }

        Node<T> cur = tail;
        while (cur != null){
            // 保存当前节点的上一个节点
            Node<T> temp = cur.prev;
            // 当前节点的上一个节点指向当前节点的下一个节点
            cur.prev = cur.next;
            // 当前节点的下一个节点指向当前节点的上一个节点
            cur.next = temp;
            // 此时当前节点的指针已经处理完成，而上一个节点的指针为变化，该节点的下一个节点依然指向当前节点
            // 上一个节点就是下一个要处理的节点
            cur = temp;
        }

        Node<T> t = tail;
        tail = head;
        head = t;
    }
}
